public class MyHashMapS {
    public class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] map;
    public int size;
    public double factor=0.75;
    public MyHashMapS(){
        this.map=new Node[8];
        this.size=0;
    }
    public int put(int key,int val){
        int index=key%map.length;
        Node cur=map[index];
        while(cur!=null){
            if(cur.val==key){
                int tmp=cur.val;
                cur.val=val;
                return tmp;
            }
            cur=cur.next;
        }
        Node node=new Node(key,val);
        node.next=map[index];
        map[index]=node;
        this.size++;
        if(this.factor<=Factory()){
            resize();
        }
        return -1;
    }
    public double Factory(){
        return this.size*1.0/this.map.length;
    }
    public void resize(){
        Node[] newMap=new Node[map.length*2];
        for(int i=0;i<map.length;i++){
            Node cur=map[i];
            Node next;
            while(cur!=null){
                next=cur.next;
                int index=cur.key%newMap.length;
                cur.next=newMap[index];
                newMap[index]=cur;
                cur=next;
            }
        }
        map=newMap;
    }
    public int get(int key){
        int index=key%map.length;
        for(Node cur=map[index];cur!=null;cur=cur.next){
            if(cur.key==key){
                return cur.val;
            }
        }
        return -1;
    }
}
